#include <bits/stdc++.h>
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

inline static int read(){
    int sum=0,neg=0,ch=getchar();
    while(!isdigit(ch)) neg|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=sum*10+(ch^48),ch=getchar();
    return neg?-sum:sum;
}
constexpr int mod=998244353;
struct{int v,nxt;}e[15000000]; int n,m,head[2005],ecnt=1;
void add(int u,int v){e[++ecnt]={v,head[u]},head[u]=ecnt;}

int Min;
namespace Solve1{
    int dep[2005]; bool vis[2005];
    void dfs(int u,int fa){
        vis[u]=1,dep[u]=dep[fa]+1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v; if(v==fa) continue;
            if(vis[v]) Min=min(Min,abs(dep[u]-dep[v])); else dfs(v,u);
        }
    }
    void solve(){
        Min=INT_MAX;
        for(int i=1;i<=n;i++) memset(vis+1,0,n),dfs(i,0);
        printf("-%d ",Min+=m-1);
    }
}

constexpr int inf=0x01010101;
namespace bf{
    int u[50],v[50],x[50],y[50],L,f[6][6],g[6][6],ans;
    void dfs(int s,int qwq){
        if(s==L+1){
            memcpy(g,f,sizeof(f));
            for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]); int sum=0;
            for(int i=1;i<=m;i++) sum+=g[u[i]][v[i]]; ans+=sum==Min; return;
        }
        if(qwq) f[x[s]][y[s]]=f[y[s]][x[s]]=1,dfs(s+1,qwq-1);
        if(L-s>=qwq) f[x[s]][y[s]]=f[y[s]][x[s]]=inf,dfs(s+1,qwq);
    }
    void solve(){
        for(int i=1,t=0;i<=n;i++) for(int j=head[i];j;j=e[j].nxt)
            if(e[j].v>i) t++,u[t]=i,v[t]=e[j].v;
        memset(f,0x01,sizeof(f)),L=ans=0;
        for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
            L++,x[L]=i,y[L]=j; dfs(1,m-1),printf("%d\n",ans);
    }
}

ll power(ll a,int b=mod-2,ll ret=1){
    for(;b;a=a*a%mod,b>>=1) if(b&1) ret=ret*a%mod;
    return ret;
}
int C[6005][2005];
signed main(){
    freopen("oi.in","r",stdin);
    freopen("oi.out","w",stdout);
    C[0][0]=1;
    for(int i=1;i<=6000;C[i][0]=1,i++) for(int j=1;j<=2000;j++)
        C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    int tid=read();
    for(int T=read();T;T--){
        n=read(),m=read(),memset(head,ecnt=0,4*n+4);
        for(int i=1,u,v;i<=m;i++) u=read(),v=read(),add(u,v),add(v,u);
        Solve1::solve();
        if(tid<=2) bf::solve();
        else if(tid<=4) n--,printf("%lld\n",C[3*n][n]*power(2*n+1)%mod);
        else puts("0");
    } return 0;
}
